// https://leetcode-cn.com/problems/implement-strstr/
class Solution {
public:
    int strStr(string haystack, string needle) {
        int ind[128];
        for (int i = 0; i < 128; i++) ind[i] = needle.size();
        for (int i = 0; needle[i]; i++)  ind[needle[i]] = needle.size() - i;
        int i = 0;
        while (i + needle.size() <= haystack.size()) {
            int flag = 1;
            for (int j = 0; needle[j]; j++) {
                if (haystack[i + j] == needle[j]) continue;;
                flag = 0;
                break;
            }
            if (flag) return i;
            i += ind[haystack[i + needle.size()]];
        }
        return -1;
    }
};